package com.jk;

import java.util.Calendar;

public class Demo2 {
    public static void main(String[] args) {
        int j;
        int n;
        //基本方法
        long start1 = Calendar.getInstance().getTimeInMillis();
        n = 1;
        for (int i = 2; i <= 20000; i++){
            for (j = 2; j <= i/2; j++){
                if(i % j == 0){
                    break;
                }
            }
            if( j > i/2){
                    System.out.print(i + "  ");
                if( n >= 5) {
                    System.out.println();
                    n = 1;
                }else{
                    n++;
                }
            }
        }
        long end1 = Calendar.getInstance().getTimeInMillis();
        System.out.println("优化前时间："+(end1-start1));

        //优化方法
        long start2 = Calendar.getInstance().getTimeInMillis();
        n = 3;
        System.out.print("2   3   ");
        for (int i = 2; i <= 20000; i++) {
            if (isPrime(i)) {
                System.out.print(i + "  ");
                if (n >= 5) {
                    System.out.println();
                    n = 1;
                } else {
                    n++;
                }
            }
        }
        long end2 = Calendar.getInstance().getTimeInMillis();
        System.out.println("\n优化后时间："+(end2-start2));
    }
    /**
     * 判断是否为素数/质数的最有效方法
     * 1.小于5的2和3
     * 2.大于等于5的素数一定和6的倍数相邻，例如5和7，11和13,17和19等等。
     * @param num
     * @return
     */
    public static boolean isPrime(int num) {
        //两个较小数另外处理
        if(num==2 || num==3) {
            return true;
        }

        //不在6的倍数两侧的一定不是素数
        if(num%6!=1 && num%6!=5) {
            return false;
        }

        int tmp = (int) Math.sqrt(num);//获取平方根
        //在6的倍数两侧的也可能不是素数
        for(int i=5; i<=tmp; i+=6) {
            if(num%i==0 || num%(i+2)==0) {
                return false;
            }
        }

        return true;
    }
}
